# -*- coding:utf-8 -*-
#!/usr/bin python3

# Import Empty
import sys

sys.path.append("../exceptions")
from empty import Empty

"""用单向列表实现队列"""


class LinkedQueue:
    """通过单链表存储方式实现先进先出的队列"""

    class _Node:
        """不共有类：用于存储单个链表结点"""

        __slot__ = "_element", "_next"

        def __init__(self, element, next_node):
            self._element = element
            self._next = next_node

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is empty!")
        return self._head._element

    def last(self):
        if self.is_empty():
            raise Empty("Queue is empty!")
        return self._tail

    def enqueue(self, e):
        new = cls._Node(e, None)
        if self.is_empty():
            self._head = new
        else:
            self._tail._next = new
        self._tail = new
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise Empty("Queue is empty!")
        ret = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty():
            self._tail = None
        return ret
